package cn.lbd.arithmetic.dp;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.stream.Collectors;

class Demo {
    private static final int MAX_SIZE = 99999;
    static int dp[] = new int[MAX_SIZE];
    static int prev[] = new int[MAX_SIZE];

    public static void main(String[] args) {
        int arr[] = new int[]{1, 2, 4, 1, 7, 8, 3};
        int n = arr.length;
        disp(arr, n);
    }

    public static void disp(int[] arr, int n) {
        longestNoncontiguousSequence(arr, n);
        //最优解下标
        int maxi = 0;
        for (int i = 1; i < n; i++) {
            if (dp[i] > dp[maxi]) {
                maxi = i;
            }
        }
        System.out.println("最优解："+dp[maxi]);
        List<Integer> list = new ArrayList();
        for (int tempPre = maxi; tempPre >= 0; tempPre = prev[tempPre]) {
            list.add(tempPre);
        }
        System.out.println("所选择的序列："+list.stream()
                .sorted(Integer::compareTo)
                .collect(Collectors.toList()).toString());

    }

    public static void longestNoncontiguousSequence(int[] arr, int n) {
        prev[0] = prev[1] = -1;
        for (int i = 0; i < n; i++) {
            if (i == 0) {
                dp[i] = arr[0];
            } else if (i == 1) {
                dp[i] = Math.max(arr[0], arr[1]);
            } else {
                dp[i] = Math.max(dp[i - 1], arr[i] + dp[i - 2]);
                prev[i] = i - 2;
            }
        }
    }
}
